"""
question-3
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
example:
输入: s = "abcabcbb"
输出: s = 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
"""
def solution(str):
    """
    暴力搜索
    """
    tmp = []
    l = 0
    for i in range(len(str)-1):
        for j in range(i,len(str)):
            if str[i] not in tmp:
                tmp.append(str[i])
                l = max(len(tmp),l)
    return l

def improved_solution(s):
    """
    滑动窗口
    """
    from collections import defaultdict
    left_pointer = 0
    right_pointer = 0
    move_sign = 0 # larger than zero means that the movement is to start
    lookup_dict = defaultdict(int) # to save the amount of char
    max_len = 0
    while right_pointer < len(s):
        if lookup_dict[s[right_pointer]] > 0:
            move_sign +=1

        lookup_dict[s[right_pointer]]+=1
        right_pointer +=1
        while move_sign > 0: # left side starts to move
            if lookup_dict[s[left_pointer]] > 1: # check first element in the left side
                move_sign -= 1
            lookup_dict[s[left_pointer]] -=1 # the element is not repeated, minus one such that the previous element will not be considered
            left_pointer+=1

        max_len = max(max_len,right_pointer-left_pointer)
    return max_len


if __name__ =="__main__":
    s = "abcabcbb"
    print(improved_solution(s))


